package com.example.demo.algorithm.lesson.basic.class2;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author liweizhi
 * @date 2020/4/23
 * 火车,两边都可以成为"头"
 */
public class DoubleEndsQueue<E> {
    public static class DoubleNode<E> {
        private E value;
        private DoubleNode<E> last;
        private DoubleNode<E> next;

        public DoubleNode(E value) {
            this.value = value;
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        public DoubleNode<E> getLast() {
            return last;
        }

        public void setLast(DoubleNode<E> last) {
            this.last = last;
        }

        public DoubleNode<E> getNext() {
            return next;
        }

        public void setNext(DoubleNode<E> next) {
            this.next = next;
        }
    }

    private DoubleNode<E> head;
    private DoubleNode<E> tail;

    public void pushHead(E value) {
        DoubleNode<E> node = new DoubleNode<>(value);
        if (head == null) {
            head = node;
            tail = node;
            return;
        }
        node.setNext(head);
        head.setLast(node);
        head = node;
    }

    public E popHead() {
        if (head == null) {
            return null;
        }
        DoubleNode<E> cur = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.getNext();
            head.setLast(null);
            cur.setNext(null);
        }
        return cur.getValue();
    }

    public void pushTail(E value) {
        DoubleNode<E> node = new DoubleNode<>(value);
        if (tail == null) {
            tail = node;
            head = node;
            return;
        }
        tail.setNext(node);
        node.setLast(tail);
        tail = node;
    }

    public E popTail() {
        if (tail == null) {
            return null;
        }
        DoubleNode<E> cur = tail;
        if (tail == head) {
            tail = null;
            head = null;
        } else {
            tail = tail.getLast();
            tail.setNext(null);
            cur.setLast(null);
        }
        return cur.getValue();
    }

    public static class MyStack<E> {
        private DoubleEndsQueue<E> linkedList = new DoubleEndsQueue<>();

        public void push(E value) {
            linkedList.pushHead(value);
        }

        public E pop() {
            return linkedList.popHead();
        }
    }

    public static class MyQueue<E> {
        private DoubleEndsQueue<E> linkedList = new DoubleEndsQueue<>();

        public void offer(E value) {
            linkedList.pushHead(value);
        }

        public E poll() {
            return linkedList.popTail();
        }
    }

    public static boolean isEqual(Integer o1, Integer o2) {
        if (o1 == null && o2 != null) {
            return false;
        }
        if (o1 != null && o2 == null) {
            return false;
        }
        if (o1 == null && o2 == null) {
            return true;
        }
        return o1.equals(o2);
    }

    public static void main(String[] args) {
        int oneTestDataNum = 100;
        int value = 10000;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            MyStack<Integer> myStack = new MyStack<>();
            MyQueue<Integer> myQueue = new MyQueue<>();
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 0; j < oneTestDataNum; j++) {
                int nums = (int) (Math.random() * value);
                if (stack.isEmpty()) {
                    myStack.push(nums);
                    stack.push(nums);
                } else {
                    if (Math.random() < 0.5) {
                        myStack.push(nums);
                        stack.push(nums);
                    } else {
                        if (!isEqual(myStack.pop(), stack.pop())) {
                            System.out.println("oops!");
                        }
                    }
                }
                int numq = (int) (Math.random() * value);
                if (stack.isEmpty()) {
                    myQueue.offer(numq);
                    queue.offer(numq);
                } else {
                    if (Math.random() < 0.5) {
                        myQueue.offer(numq);
                        queue.offer(numq);
                    } else {
                        if (!isEqual(myQueue.poll(), queue.poll())) {
                            System.out.println("oops!");
                        }
                    }
                }
            }
        }
        System.out.println("finish!");
    }
}
